package cn.bellychang.bobo.heap;

/**
 * @author ChangLiang
 * @date 2021/2/10
 */
public class MaxHeap<E extends Comparable<E>> {

    /**
     * 数组 从下标1开始存储数据
     */
    private E[] data;

    /**
     * 堆可以存储的最大数据个数
     */
    private int capacity;

    /**
     * 堆中已经存储的数据个数
     */
    private int size;

    public MaxHeap(int capacity) {
        data = (E[]) new Comparable[capacity + 1];
        this.capacity = capacity;
        size = 0;
    }

    // 取出堆中最大元素
    public E extractMax(){
        // 堆中没有数据
        if (size == 0) {
            return null;
        }
        E temp = data[1];
        data[1] = data[size];
        size--;
        heapify(1);
        return temp;
    }

    /**
     * 自上向下堆化
     */
    private void heapify(int index) {

        while (true) {
            int maxPos = index;
            // 比较左右两个子节点
            if (index * 2 <= capacity && data[index].compareTo(data[index * 2]) < 0) {
                maxPos = index * 2;
            }
            if (index * 2 + 1 <= capacity && data[maxPos].compareTo(data[index * 2 + 1]) < 0) {
                maxPos = index * 2 + 1;
            }
            if(maxPos== index){
                break;
            }
            swap(data, index, maxPos);
            index = maxPos;
        }
    }

    public void add(E e) {
        // 堆满了
        if (size >= capacity) {
            return;
        }

        size++;
        data[size] = e;

        // heapify
        int i = size;
        while (i / 2 > 0 && data[i].compareTo(data[i / 2]) > 0) {
            swap(data, i, i/2);
            i = i/2;
        }
    }

    private void swap(E[] data, int i, int j) {
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    public void printHeap() {
        int index = 1;
        int length = 1;
        int tempSize = 0;
        int allSize = 1;
        while (allSize<= size) {
            tempSize++;
            allSize++;
            System.out.print(data[index] + "   ");
            index++;
            if (length == tempSize) {
                length = length * 2;
                tempSize = 0;
                System.out.println();
            }
        }
        System.out.println();
    }
}
